

<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 13, Exercise 15<BR>

<BR>

</H1>





Consider any instance of the 0/1 knapsack problem.

Let <em class=var>O</em>

be the set of objects packed into the knapsack

in some optimal solution and

let <em class=var>PO</em> be the profit earned by this solution.

Let <em class=var>PB</em> be the profit earned by the

bounded-performance solution.

If <em class=var>O</em> has fewer than two objects,

the bounded-performance solution

must also be optimal as the bounded-performance agorithm

tries all single object packings.

So, assume that <em class=var>O</em> has more than one object.

Let <em class=var>i</em> denote the object in <em class=var>O</em>

that has maximum profit.

The profit of any other object <em class=var>j</em> in <em class=var>O</em>

is &lt;= <em class=var>PO/2</em> (otherwise, <em class=var>p<sub>i</sub> +

p<sub>j</sub> > PO</em>).

<br><br>

Consider the time the bounded-performance heuristic starts

by putting object <em class=var>i</em> into the knapsack.

Let <em class=var>B</em> denote the objects

that are packed into the knapsack at this time.

Let <em class=var>s</em> be the object with highest profit density

that is in <em class=var>O</em> but not

in <em class=var>B</em>.  If there is no such object, <em class=var>B</em>

must also be an optimal solution and the error bound is established.

<br><br>

Let <em class=var>CB</em> be the capacity used by objects other than

<em class=var>i</em> packed into the knapsack before object <em class=var>s</em>

is excluded by the greedy method.  In both <em class=var>O</em> and

<em class=var>B</em> this capacity is packed by the same objects and so earns

the same profit.  When object <em class=var>s</em> is excluded by the

greedy packing, the

available capacity is less than <em class=var>w<sub>s</sub></em>

and is filled in the optimal solution by objects with profit density

no more than

<em class=var>p<sub>s</sub>/w<sub>s</sub></em>.  So the additional profit

generated by <em class=var>O</em> is less than

<em class=var>p<sub>s</sub></em>, which is no more than

<em class=var>PO/2</em>.

<br><br>

Consequently, <em class=var>PO - PB < PO/2</em> and

<em class=var>(PO - PB)/PO < 1/2</em>.





</FONT>

</BODY>

</HTML>

